package com.wp.基本算法.排序;

import java.util.Arrays;

/**
 * Created by 王萍 on 2017/8/23 0023.
 */
//先设置一个变量h，根据array的长度来确定h的取值，一般使用while (h < length / 3) h = 3 * h + 1。
//开始排序：给以h为间隔给array中的数排序，每次循环后h=h/3.
//最后h=1，实际上是做了一次插入排序
//由于插入排序对于大部分已经排好序的数组来说，性能是很好的，所以最后一次以h=1的排序是非常快的。

//希尔排序就是基于插入排序的一种改进：先让大部分数有序，最后在进行一次插入排序。
public class 希尔排序 {

    public static void main(String[] args) {
        Comparable[] numbers = new Comparable[]{2, 3, 5, 1, 4, 9, 6};
        shellSort(numbers);
        Arrays.stream(numbers).forEach(number -> System.out.print(number + " "));

        Comparable[] chars = new Comparable[]{'w', 'a', 'n', 'g', 'p', 'i', 'n', 'g'};
        shellSort(chars);
        Arrays.stream(chars).forEach(number -> System.out.print(number + " "));
    }

    public static Comparable[] shellSort(Comparable[] array) {
        int length = array.length;
        Comparable tmp;
        int h = 1;
        while (h < length / 3) h = 3 * h + 1;
        while (h >= 1) {
            //下面两个for循环，就是插入排序。
            for (int i = h; i < length; i++) {
                for (int j = i; j - h >= 0 && array[j].compareTo(array[j - h]) < 0; j -= h) {
                    tmp = array[j];
                    array[j] = array[j - h];
                    array[j - h] = tmp;
                }
            }
            h = h / 3;
        }
        return array;
    }
}
